//UOJ 80
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>

using namespace std;

const int inf=0x3f3f3f3f;
const int maxn=405;
int w[maxn][maxn];
int lmark[maxn],rmark[maxn];
int lmate[maxn],rmate[maxn];
int lv[maxn],rv[maxn];
int slack[maxn],prev[maxn];
int q[maxn],f,r;
int curr,n;

void push(int p){
    while(p){
        int x=prev[p],y=lmate[x];
        rmate[p]=x;
        lmate[x]=p;
        p=y;
    }
}
inline bool update(int &x,int y){if(x>=y) return x=y,true;return false;}
bool findRoute(){
    for(;f<r;f++){
        const int &fro=q[f];
        for(int j=1;j<=n;j++){
            if(rmark[j]==curr) continue;
            if(w[fro][j]==lv[fro]+rv[j]){
                prev[j]=fro;
                if(!rmate[j]){
                    push(j);
                    return true;
                }
                rmark[j]=curr;
                lmark[q[r++]=rmate[j]]=curr;
            }else if(update(slack[j],lv[fro]+rv[j]-w[fro][j])) prev[j]=fro;
        }
    }
    return false;
}
bool adjust(){
    int ans=inf;
    for(int j=1;j<=n;j++) if(rmark[j]!=curr) ans=min(ans,slack[j]);
    if(ans==inf) return false;

    for(int i=1;i<=n;i++){
        if(lmark[i]==curr) lv[i]-=ans;
        if(rmark[i]==curr) rv[i]+=ans;
        else slack[i]-=ans;
    }

    for(int i=1;i<=n;i++){
        if(rmark[i]==curr||slack[i]) continue;
        if(!rmate[i]){
            push(i);
            return true;
        }else{
            rmark[i]=curr;
            lmark[q[r++]=rmate[i]]=curr;
        }
    }
    return false;
}
void KM(){
    for(curr=1;curr<=n;curr++){
        memset(slack,0x3f,sizeof slack);
        f=r=0;
        lmark[q[r++]=curr]=curr;
        while(1){
            if(findRoute()) break;
            if(adjust()) break;
        }
    }
}

int main(){
    int nl,nr,m;
    scanf("%d%d%d",&nl,&nr,&m);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        scanf("%d",&w[x][y]);
        if(w[x][y]>lv[x]) lv[x]=w[x][y];
    }
    n=max(nl,nr);
    KM();
    long long ans=0;
    for(int i=1;i<=n;i++) ans+=lv[i]+rv[i];
    printf("%lld\n",ans);
    for(int i=1;i<=nl;i++){
        if(w[i][lmate[i]]) printf("%d",lmate[i]);
        else printf("0");
        if(i<nl) putchar(' ');
    }

    return 0;
}

